package main

import (
	"fmt"
)

/**
执行用时：92 ms, 在所有 Go 提交中击败了23.65%的用户
内存消耗：9.9 MB, 在所有 Go 提交中击败了7.88%的用户
 */
func largestRectangleArea(heights []int) int {

	n := len(heights)
	h := make([]int, n + 2)
	h[0], h[n + 1] = -1, -1
	for i := 1; i <= n; i++ { h[i] = heights[i - 1] }

	stk := make([]int, 0)
	l, r := make([]int, n + 1), make([]int, n + 1)

	stk = append(stk, 0)
	for i := 1; i <= n; i++ {
		for h[stk[len(stk) - 1]] >= h[i] { stk = stk[:len(stk) - 1] }
		l[i] = stk[len(stk) - 1]
		stk = append(stk, i)
	}

	stk = stk[:0]
	stk = append(stk, n + 1)
	for i := n; i > 0; i-- {
		for h[stk[len(stk) - 1]] >= h[i] { stk = stk[:len(stk) - 1] }
		r[i] = stk[len(stk) - 1]
		stk = append(stk, i)
	}

	res := 0
	for i := 1; i <= n; i++ {
		res = max(res, h[i] * (r[i] - l[i] - 1))
	}
	return res
}

// 求最大值
func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {

	heights := []int{2, 1, 5, 6, 2, 3}
	fmt.Println(largestRectangleArea(heights))
}
